home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / basic / _dlist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  13.1 KB  |  721 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _dlist.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/impl/dlist.h>
  18. #include <ctype.h>
  19.  
  20.  
  21. #define SWAP(a,b) { register dlink* x = *a; *a = *b; *b = x; }
  22.  
  23. #define MIN_D 16 
  24.  
  25. //------------------------------------------------------------------------------
  26. // Members of class dlist: base class for all lists
  27. //------------------------------------------------------------------------------
  28.  
  29. dlist::dlist()      
  30. { h=0; 
  31.   t=0;
  32.   count=0;
  33.   iterator=0; 
  34. }
  35.  
  36. dlist::dlist(GenPtr a) 
  37. { h=t=new dlink(a,0,0);
  38.   count=1; 
  39.   iterator=0;  
  40. }
  41.  
  42. dlist::dlist(const dlist& x)
  43. { register dlink* p;
  44.  
  45.   iterator=h=t=0; 
  46.   count = 0; 
  47.                               
  48.   for (p = x.h; p; p = p->succ) append(p->e); 
  49.  
  50.   if (!int_type())
  51.     for (p = h; p; p = p->succ) x.copy_el(p->e);
  52. }
  53.  
  54.  
  55. void dlist::recompute_length() const
  56. { int n = 0;
  57.   for(dlink* it = h; it; it = it->succ)  n++;
  58.   (int&)count = n;
  59. }
  60.  
  61.  
  62. //------------------------------------------------------------------------------
  63. // Iteration:
  64. //------------------------------------------------------------------------------
  65.  
  66. dlink* dlist::move_iterator(int dir) const 
  67. { if (iterator) 
  68.      set_iterator(dir ? iterator->pred : iterator->succ);
  69.   else 
  70.      set_iterator(dir ? t : h);
  71.   return iterator;
  72.  } 
  73.  
  74. bool dlist::current_element(GenPtr& x) const 
  75. { if (iterator) 
  76.   { x = iterator->e; 
  77.     return true; 
  78.    } 
  79.   return false; 
  80.  }
  81.  
  82. bool dlist::next_element(GenPtr& x)    const 
  83. { if (iterator) 
  84.      set_iterator(iterator->succ);
  85.   else 
  86.      set_iterator(h);
  87.  
  88.   if (iterator) 
  89.   { x = iterator->e;
  90.     return true; 
  91.    } 
  92.   return false; 
  93.  }
  94.  
  95. bool dlist::prev_element(GenPtr& x)  const
  96. { if (iterator) 
  97.      set_iterator(iterator->pred);
  98.   else 
  99.      set_iterator(t);
  100.  
  101.   if (iterator) 
  102.   { x = iterator->e;
  103.     return true; 
  104.    } 
  105.   return false; 
  106.  }
  107.  
  108. //------------------------------------------------------------------------------
  109.  
  110. dlink* dlist::get_item(int i) const
  111. { dlink* p = h;
  112.   while ( p && i--) p = p->succ; 
  113.   return p;
  114. }
  115.  
  116. dlink* dlist::succ(dlink* p, int i)  const
  117. { while ( p && i--) p = p->succ; 
  118.   return p;
  119. }
  120.  
  121. dlink* dlist::pred(dlink* p, int i) const
  122. { while ( p && i--) p = p->pred; 
  123.   return p;
  124. }
  125.  
  126. dlink* dlist::search(GenPtr x) const  /* linear search */
  127. { dlink* p = h;
  128.   while ( p && cmp(p->e,x)) p = p->succ; 
  129.   return p;
  130. } 
  131.  
  132. int dlist::rank(GenPtr x)   const   /* rank by linear search */
  133. { dlink* p = h;
  134.   int r = 1;
  135.   while ( p && cmp(p->e,x)) 
  136.   { p = p->succ; 
  137.     r++;
  138.    }
  139.   return (p) ? r : 0;
  140. } 
  141.  
  142. GenPtr dlist::pop()    
  143. { if (h==nil) return nil;
  144.   if (iterator!=0) error_handler(1,"pop: deletion while iterator is active");
  145.   dlink* x=h; 
  146.   h = h->succ;
  147.   if (h) h->pred = 0;
  148.   else t = nil;
  149.   GenPtr p = x->e;
  150.   delete x;
  151.   count--;
  152.   return p;
  153. }
  154.  
  155.  
  156. GenPtr dlist::Pop()    
  157. { if (h==nil) return 0;
  158.   if (iterator!=0) error_handler(1,"Pop: deletion while iterator is active");
  159.   dlink* x=t; 
  160.   t = t->pred;
  161.   if (t) t->succ = 0;
  162.   else h = nil;
  163.   GenPtr p = x->e;
  164.   delete x;
  165.   count--;
  166.   return p;
  167. }
  168.  
  169. dlink* dlist::insert(GenPtr a, dlink* l, int dir) 
  170. { 
  171.   if (iterator!=0) error_handler(2,"insert: insertion while iterator is active");
  172.  
  173.   if (l==0) return dir ? append(a) : push(a); 
  174.  
  175.   dlink* s=l->succ;
  176.   dlink* p=l->pred;
  177.   dlink* n;
  178.   
  179.   if (dir==0) //insert after l
  180.   { n= new dlink(a,l,s);
  181.     l->succ = n;
  182.     if (l==t) t=n;
  183.     else s->pred = n;}
  184.  
  185.   else //insert before l
  186.   { n= new dlink(a,p,l);
  187.     l->pred = n;
  188.     if (l==h) h=n;
  189.     else p->succ = n;}
  190.  
  191.   count++;
  192.  
  193.   return n;
  194. }
  195.  
  196.  
  197. void dlist::conc(dlist& l, int dir)
  198. { 
  199.   if (iterator!=0) error_handler(2,"conc: iterator is active");
  200.  
  201.   if (h==nil)
  202.    { h = l.h; 
  203.      t = l.t; 
  204.     }
  205.   else
  206.   { if (dir==0)  // append l 
  207.     { t->succ = l.h;
  208.       if (l.h) { l.h->pred = t; t = l.t; } 
  209.      }
  210.     else // prepend l
  211.     { h->pred = l.t;
  212.       if (l.t) { l.t->succ= h; h = l.h; } 
  213.      }
  214.    }
  215.  
  216.  count += l.count;
  217.  
  218.  l.h = l.t = 0;
  219.  l.count = 0;
  220. }
  221.  
  222.  
  223. void dlist::split(dlink* p, dlist& l1, dlist& l2, int dir)
  224. { 
  225.    // split L at item p into l1 and l2 and  L is made empty
  226.    // dir = 0: p becomes first item of l2 (l2 empty if p == nil)
  227.    // dir = 1: p becomes last item of l1 (l1 empty if p == nil)
  228.  
  229.    if (iterator!=0) 
  230.    error_handler(1,"list: split while iterator is active");
  231.  
  232.   if (h == 0) error_handler(888,"split on empty list");
  233.  
  234.   l1.clear();
  235.   l2.clear();
  236.  
  237.   if (dir && p) { p = p->succ; dir = 0; }
  238.  
  239.   if (p==nil) 
  240.    { if (dir==0)
  241.       { l2.h = h;
  242.         l2.t = t;
  243.         l2.count = count;
  244.        }
  245.      else
  246.       { l1.h = h;
  247.         l1.t = t;
  248.         l1.count = count;
  249.        }
  250.     }
  251.   else // p != nil
  252.    { if (p->pred)
  253.      { l1.h = h;
  254.        l1.t = p->pred;
  255.        p->pred->succ = 0;
  256.        l1.count = -1;   // do not know length of l1
  257.       }
  258.  
  259.      p->pred = 0;
  260.      l2.h = p;
  261.      l2.t = t;
  262.      l2.count = -1;   // do not know length of l2
  263.     }
  264.  
  265.   // make original list empty
  266.   h = t = 0;
  267.   count = 0;
  268.  
  269. }
  270.  
  271.  
  272.  
  273. GenPtr dlist::del(dlink* it)
  274. { if (iterator) error_handler(1,"dlist: deletion while iterator is active");
  275.   if (it==nil)  error_handler(999,"dlist: delete nil-item");
  276.   if (it==h)  return pop();
  277.   if (it==t)  return Pop();
  278.   dlink*  p = it->pred;
  279.   dlink*  s = it->succ;
  280.   GenPtr x = it->e;
  281.   p->succ = s;
  282.   s->pred = p;
  283.   count--;
  284.   delete it;
  285.   return x;
  286. }
  287.  
  288. dlink* dlist::cyclic_succ(dlink* it) const
  289. { if (it==0) return 0;
  290.   return it->succ? it->succ : h;
  291. }
  292.  
  293. dlink* dlist::cyclic_pred(dlink* it) const
  294. { if (it==0) return 0;
  295.   return it->pred? it->pred : t;
  296. }
  297.  
  298.  
  299. dlink* dlist::max(CMP_PTR f) const
  300. { if (h==0) return 0;
  301.   dlink* m=h;
  302.   dlink* p=m->succ;
  303.  
  304.   if (f) 
  305.      while (p)
  306.      { if (f(p->e,m->e) > 0) m=p;
  307.        p=p->succ;
  308.       }
  309.   else
  310.      while (p)
  311.      { if (cmp(p->e,m->e) > 0) m=p;
  312.        p=p->succ;
  313.       }
  314.  
  315.   return m;
  316. }
  317.  
  318. dlink* dlist::min(CMP_PTR f) const
  319. { if (h==0) return 0;
  320.   dlink* m=h;
  321.   dlink* p=m->succ;
  322.  
  323.   if (f)
  324.      while (p)
  325.      { if (f(p->e,m->e) < 0) m=p;
  326.        p=p->succ;
  327.      }
  328.   else 
  329.      while (p)
  330.      { if (cmp(p->e,m->e) < 0) m=p;
  331.        p=p->succ;
  332.       }
  333.  
  334.   return m;
  335. }
  336.  
  337.  
  338. void dlist::apply(APP_PTR apply)
  339. { register dlink* p = h;
  340.   while (p)
  341.   { apply(p->e);
  342.     p = p->succ;
  343.    }
  344. }
  345.  
  346. void dlist::permute()
  347. { 
  348.   if (iterator!=0) 
  349.           error_handler(3,"permute: modification while iterator is active");
  350.  
  351.   list_item* A = new list_item[count+2];
  352.   list_item x = h;
  353.   int j;
  354.  
  355.   A[0] = A[count+1] = 0;
  356.  
  357.   for(j=1; j <= count; j++)
  358.   { A[j] = x;
  359.     x = x->succ;
  360.    }
  361.  
  362.   for(j=1; j<count; j++)  
  363.   { long r = random(j,count);
  364.     x = A[j];
  365.     A[j] = A[r];
  366.     A[r] = x;
  367.    }
  368.  
  369.   for(j=1; j<=count; j++) 
  370.   { A[j]->succ = A[j+1];
  371.     A[j]->pred = A[j-1];
  372.    }
  373.  
  374.   h = A[1];
  375.   t = A[count];
  376.   
  377.   delete A;
  378. }
  379.         
  380.  
  381. void dlist::bucket_sort(int i, int j, ORD_PTR ord)
  382. { if (iterator!=0) 
  383.         error_handler(3,"bucket_sort: modification while iterator is active");
  384.  
  385.   if (h==nil) return; // empty list
  386.  
  387.   int n = j-i+1;
  388.  
  389.   register list_item* bucket= new list_item[n+1];
  390.   register list_item* stop = bucket + n;
  391.   register list_item* p;
  392.  
  393.   register list_item q;
  394.   register list_item x;
  395.  
  396.   for(p=bucket;p<=stop;p++)  *p = 0;
  397.  
  398.   while (h) 
  399.   { x = h; 
  400.     h = h->succ;
  401.     int k = ord(x->e);
  402.     if (k >= i && k <= j) 
  403.      { p = bucket+k-i;
  404.        x->pred = *p;
  405.        if (*p) (*p)->succ = x;
  406.        *p = x;
  407.       }
  408.     else 
  409.        error_handler(4,"bucket_sort: value out of range") ;
  410.    }
  411.  
  412.  for(p=stop; *p==0; p--); 
  413.  
  414.  // now p points to the end of the rightmost non-empty bucket
  415.  // make it the new head  of the list (remember: list is not empty)
  416.  
  417.  t = *p;
  418.  t->succ = nil;
  419.  
  420.  for(q = *p; q->pred; q = q->pred); // now q points to the start of this bucket
  421.  
  422.  // link buckets together from right to left:
  423.  // q points to the start of the last bucket
  424.  // p points to end of the next bucket
  425.  
  426.  while(--p >= bucket) 
  427.    if (*p)
  428.    { (*p)->succ = q;
  429.      q->pred = *p;
  430.      for(q = *p; q->pred; q = q->pred); 
  431.     }
  432.  
  433.  h = q;   // head = start of leftmost non-empty bucket
  434.  
  435.  delete bucket;
  436. }
  437.  
  438.  
  439. void dlist::quick_sort(dlink** l, dlink** r)
  440. { // use virtual cmp function
  441.  
  442.   register dlink** i = l+(r-l)/2; //random()%(r-l);
  443.   register dlink** k;
  444.  
  445.   if (cmp((*i)->e,(*r)->e)>0) SWAP(i,r);
  446.  
  447.   SWAP(l,i);
  448.  
  449.   GenPtr s = (*l)->e;
  450.  
  451.   i = l;
  452.   k = r;
  453.  
  454.   for(;;)
  455.   { while (cmp((*(++i))->e,s)<0);
  456.     while (cmp((*(--k))->e,s)>0);
  457.     if (i<k) SWAP(i,k) else break;
  458.    }
  459.  
  460.   SWAP(l,k);
  461.  
  462.   if (k > l+MIN_D) quick_sort(l,k-1);
  463.   if (r > k+MIN_D) quick_sort(k+1,r);
  464. }
  465.         
  466. void dlist::quick_sort(dlink** l, dlink** r, CMP_PTR usr_cmp)
  467. { // use parameter usr_cmp
  468.  
  469.   register dlink** i = l+(r-l)/2; //random()%(r-l);
  470.   register dlink** k;
  471.  
  472.   if (usr_cmp((*i)->e,(*r)->e)>0) SWAP(i,r);
  473.  
  474.   SWAP(l,i);
  475.  
  476.   GenPtr s = (*l)->e;
  477.  
  478.   i = l;
  479.   k = r;
  480.  
  481.   for(;;)
  482.   { while (usr_cmp((*(++i))->e,s)<0);
  483.     while (usr_cmp((*(--k))->e,s)>0);
  484.     if (i<k) SWAP(i,k) else break;
  485.    }
  486.  
  487.   SWAP(l,k);
  488.  
  489.   if (k > l+MIN_D) quick_sort(l,k-1,usr_cmp);
  490.   if (r > k+MIN_D) quick_sort(k+1,r,usr_cmp);
  491. }
  492.         
  493.  
  494. void dlist::int_quick_sort(dlink** l, dlink** r)
  495. { // use built-in < and > operators for integers
  496.  
  497.   register dlink** i = l+(r-l)/2; //random()%(r-l);
  498.   register dlink** k;
  499.  
  500.   if ((*i)->e > (*r)->e) SWAP(i,r);
  501.  
  502.   SWAP(l,i);
  503.  
  504.   GenPtr s = (*l)->e;
  505.  
  506.   i = l;
  507.   k = r;
  508.  
  509.   for(;;)
  510.   { while ((*(++i))->e < s);
  511.     while ((*(--k))->e > s);
  512.     if (i<k) SWAP(i,k) else break;
  513.    }
  514.  
  515.   SWAP(l,k);
  516.  
  517.   if (k > l+MIN_D) int_quick_sort(l,k-1);
  518.   if (r > k+MIN_D) int_quick_sort(k+1,r);
  519. }
  520.  
  521.  
  522. void dlist::insertion_sort(dlink** l, dlink** r, dlink** min_stop, 
  523.                                CMP_PTR usr_cmp)
  524. {
  525.   register dlink** min=l;
  526.   register dlink** run;
  527.   register dlink** p;
  528.   register dlink** q;
  529.  
  530.   for (run = l+1; run <= min_stop; run++)
  531.       if (usr_cmp((*run)->e,(*min)->e) < 0) min = run;
  532.  
  533.   SWAP(min,l);
  534.  
  535.   if (r == l+1) return; 
  536.  
  537.   for(run=l+2; run <= r; run++)
  538.   { for (min = run-1; usr_cmp((*run)->e,(*min)->e) < 0; min--);
  539.     min++;
  540.     if (run != min) 
  541.     { dlink* save = *run;
  542.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  543.       *min = save;
  544.      }
  545.    }
  546. }
  547.  
  548.  
  549. void dlist::insertion_sort(dlink** l, dlink** r, dlink** min_stop)
  550. {
  551.   register dlink** min=l;
  552.   register dlink** run;
  553.   register dlink** p;
  554.   register dlink** q;
  555.  
  556.   for (run = l+1; run <= min_stop; run++)
  557.       if (cmp((*run)->e,(*min)->e) < 0) min = run;
  558.  
  559.   SWAP(min,l);
  560.  
  561.   if (r == l+1) return; 
  562.  
  563.   for(run=l+2; run <= r; run++)
  564.   { for (min = run-1; cmp((*run)->e,(*min)->e) < 0; min--);
  565.     min++;
  566.     if (run != min) 
  567.     { dlink* save = *run;
  568.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  569.       *min = save;
  570.      }
  571.    }
  572. }
  573.  
  574.  
  575. void dlist::int_insertion_sort(dlink** l, dlink** r, dlink** min_stop)
  576. {
  577.   register dlink** min=l;
  578.   register dlink** run;
  579.   register dlink** p;
  580.   register dlink** q;
  581.  
  582.   for (run = l+1; run <= min_stop; run++)
  583.       if ((*run)->e < (*min)->e) min = run;
  584.  
  585.   SWAP(min,l);
  586.  
  587.   if (r == l+1) return; 
  588.  
  589.   for(run=l+2; run <= r; run++)
  590.   { for (min = run-1; (*run)->e < (*min)->e; min--);
  591.     min++;
  592.     if (run != min) 
  593.     { dlink* save = *run;
  594.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  595.       *min = save;
  596.      }
  597.    }
  598. }
  599.  
  600.  
  601.  
  602.  
  603. void dlist::sort(CMP_PTR f)
  604. { if (iterator!=0)
  605.       error_handler(1,"sort: modification while iterator is active");
  606.  
  607.   if (count<=1) return;    // nothing to sort
  608.  
  609.   dlink** A = new dlink*[count+2];
  610.  
  611.   register dlink*  loc = h;
  612.   register dlink** p;
  613.   register dlink** stop = A+count+1;
  614.  
  615.   dlink** left  = A+1;
  616.   dlink** right = A+count;
  617.   dlink** min_stop = left + MIN_D;
  618.  
  619.   if (min_stop > right) min_stop = right;
  620.  
  621. min_stop = right;
  622.  
  623.   for(p=A+1; p<stop; p++)
  624.   { *p = loc;
  625.     loc = loc->succ;
  626.    }
  627.  
  628.  
  629.   if (f)
  630.     { quick_sort(left,right,f);
  631.       insertion_sort(left,right,min_stop,f);
  632.      }
  633.   else  
  634.     if (int_type())
  635.       { int_quick_sort(left,right);
  636.         int_insertion_sort(left,right,min_stop);
  637.        }
  638.     else
  639.       { quick_sort(left,right);
  640.         insertion_sort(left,right,min_stop);
  641.        }
  642.  
  643.   *A = *stop = 0;
  644.  
  645.   for (p=A+1;p<stop;p++) 
  646.   { (*p)->succ = *(p+1);
  647.     (*p)->pred = *(p-1);
  648.    }
  649.  
  650.   h = A[1];
  651.   t = A[count];
  652.  
  653.   delete A;
  654. }
  655.  
  656.  
  657. dlist& dlist::operator=(const dlist& x)
  658. { register dlink* p;
  659.  
  660.   clear();
  661.  
  662.   for (p = x.h; p; p = p->succ) append(p->e); 
  663.  
  664.   if (!int_type())
  665.     for (p = h; p; p = p->succ) copy_el(p->e);
  666.                                 
  667.   return *this;
  668. }
  669.  
  670.  
  671. dlist dlist::operator+(const dlist& x)  // concatenation
  672. { dlist y = x;
  673.   dlink* p = t;
  674.   while (p) { y.push(p->e);    
  675.               x.copy_el(p->e);
  676.               p = p->pred;}
  677.   return y;
  678. }
  679.  
  680.  
  681. void dlist::clear()
  682. { if (h==nil) return;
  683.  
  684.   if (!int_type())
  685.     for(dlink* p = h; p; p = p->succ) clear_el(p->e);
  686.  
  687.   deallocate_list(h,t,sizeof(dlink));
  688.   iterator=h=t=nil;
  689.   count=0;
  690. }
  691.  
  692. void dlist::print(ostream& out, string s, char space) const
  693. { list_item l = h;
  694.   cout << s;
  695.   if (l)
  696.   { print_el(l->e,out); 
  697.     l = l->succ;
  698.     while (l)
  699.       { out << string(space);
  700.         print_el(l->e,out); 
  701.         l = l->succ;
  702.        }
  703.   }
  704.   out.flush();
  705. }
  706.  
  707.  
  708. void dlist::read(istream& in, string s, char delim)
  709. { char c;
  710.   GenPtr x;
  711.   cout << s;
  712.   clear();
  713.   for(;;)
  714.   { while (in.get(c) && isspace(c) && c!=delim);
  715.     if (!in || c==delim) break;
  716.     in.putback(c);
  717.     read_el(x,in); 
  718.     append(x);
  719.    }
  720. }
  721.